'''
    定义单向链表，给定一个列表实现删除列表中的重复元素
    python 中没有像c++那样的数据结构。python中一切皆对象
'''
class Node:
    def __init__(self,elem):
        '''
        :param elem:用户存储节点中的数据
                next:代表指针，指向下一个节点
        '''
        self.elem = elem
        self.next = None

class SingalLinkNode:
    def __init__(self,node=None):
        '''
        :param node: 链表是一个类，有一个初始值就是链表的头节点
        这里初始化一个空链表
        '''
        self.__head = node

    def length(self):
        '''
        判断链表的长度
        :return:
        '''
        cur = self.__head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def is_empty(self):
        '''
        判断链表是否为空
        :return:
        '''
        if self.__head == None:
            return True
        else:
            return False

    def add(self,item):
        '''
        头插法
        :return:
        '''
        if self.is_empty():
            self.__head = Node(item)
        else:
            cur = self.__head
            node = Node(item)
            node.next = cur
            self.__head = node
    def append(self,item):
        '''
        尾插法
        :return:
        '''
        cur = self.__head
        if self.is_empty():
            #如果是空链表，直接在头部进行插入
            self.__head = Node(item)
        else:
            #如果不是空链表就去遍历找到最后的节点
            while cur.next:
                cur = cur.next
            node = Node(item)
            cur.next = node
    def inster(self,pos,item):
        '''
        :param pos: 插入的位置
        :param item: 插入的值
        :return:
        '''
        cur = self.__head
        index = 0
        if pos <= index:
             self.add(item)
        elif pos>(self.length()-1):
             self.append(item)
        else:
            while index < (pos - 1):
                index += 1
                cur = cur.next
            node = Node(item)
            node.next = cur.next
            cur.next = node

    def remove(self,item):
        '''
        删除指定元素的节点
        :param item:
        :return:
        '''
        cur = self.__head
        pre = None
        index = 0
        while cur.elem!=item:
             pre = cur
             cur = cur.next
             index+=1
             if cur==None:
                 print("删除的元素不存在")
                 break
        if index==0:
            self.__head = cur.next
        else:
            pre.next = cur.next

    def delete(self,pos):
        '''
        删除指定位置的节点
        :param pos:
        :return:
        '''
        if pos<0 or pos>(self.length()-1):
            print("你输入的位置超出链表的范围")
        else:
            cur = self.__head
            pre = None
            index = 0
            while pos!=index:
                index+=1
                pre = cur
                cur = cur.next
            if index!=0:
                pre.next = cur.next
            else:
                self.__head = cur.next

    def serch(self,pos):
        '''
        查询指定位置的值
        :param pos:
        :return:
        '''
        if pos < 0 or pos > (self.length() - 1):
            return "你输入的位置超出链表的范围"
        else:
            index = 0
            cur = self.__head
            while pos!=index:
                index +=1
                cur = cur.next
            return cur.elem

    def check(self,item):
        '''
        查询指定值的位置
        :param item:
        :return:
        '''
        cur = self.__head
        index = 0
        while cur.elem!=item:
            index +=1
            cur = cur.next
            if index == self.length():
                print("你查询的值不存在")
                break
        return index

    def removeDuplicateNodes(self):
        '''
        删除链表中的重复元素
        :return:
        '''
        list_ = [ ]
        cur = self.__head
        pre = None
        if not self.is_empty():
            while cur:
                if cur.elem in list_:
                    pre.next = cur.next
                    cur = pre.next
                else:
                    list_.append(cur.elem)
                    pre = cur
                    cur = cur.next
        else:
            print("链表为空")
    def display(self):
        cur = self.__head
        while cur:
            print(cur.elem,end=" ")
            cur = cur.next
        print("")
if __name__ == "__main__":
    l = SingalLinkNode()
    l.append(1)
    l.append(1)
    l.append(3)
    l.append(1)
    l.append(2)
    l.append(3)
    l.display()
    l.removeDuplicateNodes()
    l.display()
